package cn.edu.xjtu.work.reverseList;

import java.util.Stack;

/**
 * 反转链表
 * 
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class Solution {
  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    ListNode temp = head;
    for (int i = 0; i < 5; i++) {
      temp.next = new ListNode(i + 2);
      temp = temp.next;
    }
    // print(head);
    ListNode ret = reverseList1(head);
    print(ret);
  }

  public static void print(ListNode head) {
    ListNode temp = head;
    while (temp != null) {
      System.out.println(temp.val);
      temp = temp.next;
    }
  }

  /**
   * 双链表求解
   * 
   * 双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表
   * 
   * @param head
   * @return
   */
  public static ListNode reverseList(ListNode head) {
    if (head == null) {
      return null;
    }
    ListNode ret = null;
    ListNode temp = head;
    while (temp != null) {
      ret = new ListNode(temp.val, ret);
      temp = temp.next;
      // ret = temp;
    }
    return ret;
  }

  /**
   * 使用栈解决
   * 
   * @param head
   * @return
   */
  public static ListNode reverseList1(ListNode head) {
    if (head == null) {
      return null;
    }
    Stack<Integer> s = new Stack<>();
    ListNode temp = head;
    while (temp != null) {
      s.push(temp.val);
      temp = temp.next;
    }
    ListNode ret = new ListNode();
    temp = ret;
    while (!s.isEmpty()) {
      temp.next = new ListNode(s.pop(), null);
      temp = temp.next;
    }
    return ret.next;
  }

}
